//// -*- coding: utf-8 -*-
///**
// * Project: AlgorithmsLearn
// *
// * @author: yanking
// * Create time: 2022-03-17 19:52
// * IDE: IntelliJ IDEA
// * Introduction:
// */
//package com.LeetCodeT.Hash;
//
//import org.junit.jupiter.api.Test;
//
//import java.util.*;
//
//@SuppressWarnings("All")
///**
// * 使用双向链表 + Hash表实现O(1)复杂度的操作
// * @param capacity
// */
//
//@SupressWarnning("ALL")
//class LFUCache {
//
//    class Item {
//        Item l, r;
//        int k, v;
//        public Item(int _k, int _v) {
//            k = _k;
//            v = _v;
//        }
//    }
//
//    class Bucket {
//        Bucket l, r;
//        int idx;
//        Item head, tail;
//        Map<Integer, Item> map = new HashMap<>();
//        public Bucket(int _idx) {
//            idx = _idx;
//            head = new Item(-1, -1);
//            tail = new Item(-1, -1);
//            head.r = tail;
//            tail.l = head;
//        }
//        void put(int key, int value) {
//            Item item = null;
//            if (map.containsKey(key)) {
//                item = map.get(key);
//                // 更新值
//                item.v = value;
//                // 在原来的双向链表位置中移除
//                item.l.r = item.r;
//                item.r.l = item.l;
//            } else {
//                item = new Item(key, value);
//                // 添加到哈希表中
//                map.put(key, item);
//            }
//            // 增加到双向链表头部
//            item.r = head.r;
//            item.l = head;
//            head.r.l = item;
//            head.r = item;
//        }
//        Item remove(int key) {
//            if (map.containsKey(key)) {
//                Item item = map.get(key);
//                // 从双向链表中移除
//                item.l.r = item.r;
//                item.r.l = item.l;
//                // 从哈希表中移除
//                map.remove(key);
//                return item;
//            }
//            return null; // never
//        }
//        Item clear() {
//            // 从双向链表尾部找到待删除的节点
//            Item item = tail.l;
//            item.l.r = item.r;
//            item.r.l = item.l;
//            // 从哈希表中移除
//            map.remove(item.k);
//            return item;
//        }
//        boolean isEmpty() {
//            return map.size() == 0;
//        }
//    }
//
//    Map<Integer, Bucket> map = new HashMap<>();
//    Bucket head, tail;
//    int n;
//    int cnt;
//    public LFUCache(int capacity) {
//        n = capacity;
//        cnt = 0;
//        head = new Bucket(-1);
//        tail = new Bucket(-1);
//        head.r = tail;
//        tail.l = head;
//    }
//
//    public int get(int key) {
//        if (map.containsKey(key)) {
//            Bucket cur = map.get(key);
//
//            Bucket target = null;
//            if (cur.r.idx != cur.idx + 1) {
//                // 目标桶空缺
//                target = new Bucket(cur.idx + 1);
//                target.r = cur.r;
//                target.l = cur;
//                cur.r.l = target;
//                cur.r = target;
//            } else {
//                target = cur.r;
//            }
//
//            // 将当前键值对从当前桶移除，并加入新的桶
//            Item remove = cur.remove(key);
//            target.put(remove.k, remove.v);
//            // 更新当前键值对所在桶信息
//            map.put(key, target);
//
//            // 如果在移除掉当前键值对后，当前桶为空，则将当前桶删除（确保空间是 O(n) 的）
//            // 也确保调用编号最小的桶的 clear 方法，能够有效移除掉一个元素
//            deleteIfEmpty(cur);
//
//            return remove.v;
//        }
//        return -1;
//    }
//
//    public void put(int key, int value) {
//        if (n == 0) return;
//        if (map.containsKey(key)) {
//            // 元素已存在，修改一下值
//            Bucket cur = map.get(key);
//            cur.put(key, value);
//            // 调用一下 get 实现「使用次数」+ 1
//            get(key);
//        } else {
//            // 容器已满，需要先删除元素
//            if (cnt == n) {
//                // 从第一个桶（编号最小、使用次数最小）中进行清除
//                Bucket cur = head.r;
//                Item clear = cur.clear();
//                map.remove(clear.k);
//                cnt--;
//
//                // 如果在移除掉键值对后，当前桶为空，则将当前桶删除（确保空间是 O(n) 的）
//                // 也确保调用编号最小的桶的 clear 方法，能够有效移除掉一个元素
//                deleteIfEmpty(cur);
//            }
//
//            // 需要将当前键值对增加到 1 号桶
//            Bucket first = null;
//
//            // 如果 1 号桶不存在则创建
//            if (head.r.idx != 1) {
//                first = new Bucket(1);
//                first.r = head.r;
//                first.l = head;
//                head.r.l = first;
//                head.r = first;
//            } else {
//                first = head.r;
//            }
//
//            // 将键值对添加到 1 号桶
//            first.put(key, value);
//            // 更新键值对所在桶信息
//            map.put(key, first);
//            // 计数器加一
//            cnt++;
//        }
//    }
//
//    void deleteIfEmpty(Bucket cur) {
//        if (cur.isEmpty()) {
//            cur.l.r = cur.r;
//            cur.r.l = cur.l;
//            cur = null; // help GC
//        }
//    }
//}
//
//
//public class LFUCache {
//    /**
//     * 用于快速找到双向链表的节点位置
//     */
//    Map<Integer, TreeNode> map = new HashMap<>();
//    Map<Integer, Integer> data = new HashMap<>();
//    TreeNode hh, tt;
//    int capacity;
//
//    class TreeNode {
//        // Set<Integer> set = new HashSet<>();
//        // 使用set无法获取数据，删除最久未使用的数据的时候无法在map中删除最久未使用的数据，但是使用list无法在O(1)的复杂度下实现对list的更新
//        List<Integer> set = new ArrayList<>();
//        /**
//         * 这里的map用来记录当前节点存储的元素在列表中的索引
//         * key对应于元素，value对应于索引
//         */
//        Map<Integer, Integer> map = new HashMap<>();
//        int cnt;
//        TreeNode left, right;
//
//        public TreeNode(int cnt) {
//            this.cnt = cnt;
//        }
//    }
//
//
//    void clear(TreeNode node) {
//        // 双向链表变更数据的时候需要清楚空节点
//        if (node.set.size() == 0) {
//            node.right.left = node.left;
//            node.left.right = node.right;
//        }
//    }
//
//    public LFUCache(int capacity) {
//        hh = new TreeNode(-1000);
//        tt = new TreeNode(-1000);
//        hh.right = tt;
//        tt.left = hh;
//        this.capacity = capacity;
//    }
//
//    /**
//     * 数据插入 -> 应该小于capacity -> 当容量满了需要删除最近最久没有使用的数据
//     * 然后插入最新的数据
//     *
//     * @param key
//     * @return
//     */
//    public int get(int key) {
//        if (!data.containsKey(key)) {
//            // 数据结构中不存在该索引
//            return -1;
//        } else {
//            /*
//                数据结构中存在该元素，返回该索引并且更新元素的访问数量
//             */
//            TreeNode node = map.get(key);
//            TreeNode next = null;
//            if (node.right.cnt == node.cnt + 1) {
//                next = node.right;
//            } else {
//                next = new TreeNode(node.cnt + 1);
//                next.right = node.right;
//                node.right.left = next;
//                node.right = next;
//                next.left = node;
//            }
//            int index = node.map.get(key);
//            node.set.remove(index);
//            node.map.remove(key);
//            next.set.add(key);
//            next.map.put(key, node.set.size());
//            // 从节点中删除一个元素的时候，一般都要对节点进行清理，防止双向链表中出现空节点
//            clear(node);
//            map.put(key, next);
//            /*
//                数据结构中的data中的数据不用改变，因为只是访问数据，并没有对数据的value进
//                行
//                更改
//             */
//        }
//        return data.get(key);
//    }
//
//    public void put(int key, int value) {
//        TreeNode node = map.get(key);
//        TreeNode next = null;
//        if (node != null) {
//            /*
//                节点中存在包含该键值的数据,清楚当前节点内该节点的数据，然后插入新节点，此时不需要对存储空间进行判断
//                因为此时的插入操作仅仅是更该节点的数据
//             */
//            node.set.remove(key);
//            node.map.remove(key);
//            if (node.right.cnt == node.cnt + 1) {
//                next = node.right;
//            } else {
//                // 第一个节点存储的不是更改次数为一的数据，则创建并且插入新节点
//                next = new TreeNode(node.cnt + 1);
//                node.right.left = next;
//                next.left = node;
//                next.right = node.right;
//                node.right = next;
//            }
//        } else {
//            // 节点中不包含该键值对应的数据
//            if (capacity <= 0) {
//                // 空间不足需要删除最久没有使用的数据
//                // 节点链表内最久未使用的元素处于列表的0索引处，因为新来的元素都是直接插入到后面，而且访问更新的元素会被删除
//                Integer k = hh.right.set.remove(0);
//                // 删除最久未使用元素
//                hh.right.map.remove(k);
//                map.remove(k);
//                data.remove(k);
//            } else {
//                capacity--;
//            }
//            if (hh.right.cnt == 1) {
//                // 第一个节点存储的更改次数的数据为1
//                next = hh.right;
//            } else {
//                // 第一个节点存储的不是更改次数为一的数据
//                next = new TreeNode(1);
//                next.right = hh.right;
//                hh.right.left = next;
//                next.left = hh;
//                hh.right = next;
//            }
//        }
//        /*
//            list列表添加元素默认是从表位进行添加
//         */
//        next.set.add(key);
//                /*
//                    记录当前元素在节点列表中索引的位置，方便元素的定位和更新
//                 */
//        next.map.put(key, next.set.size() - 1);
//        map.put(key, next);
//        data.put(key, value);
//        if (node != null) {
//            clear(node);
//        }
//    }
//
//    public static void main(String[] args) {
//        LFUCache lf = new LFUCache(2);
//        lf.put(1, 1);
//        lf.put(2, 2);
//        System.out.println(lf.get(1));
//        lf.put(3, 3);
//        System.out.println(lf.get(2));
//        System.out.println(lf.get(3));
//        lf.put(4, 4);
//        System.out.println(lf.get(1));
//        System.out.println(lf.get(3));
//        System.out.println(lf.get(4));
//
//    }
//
//
//}
//
///**
// * Your LFUCache object will be instantiated and called as such:
// * LFUCache obj = new LFUCache(capacity);
// * int param_1 = obj.get(key);
// * obj.put(key,value);
// */